Search results for "minimum degree"
showing 6 items of 6 documents
Refined Finiteness and Degree Properties in Graphs
2020
Summary In this article the finiteness of graphs is refined and the minimal and maximal degree of graphs are formalized in the Mizar system [3], based on the formalization of graphs in [4].
Estimating the length of minimal spanning trees in compression of files
1984
Compression of a formatted file by a minimal spanning tree (MST) is studied. Here the records of the file are considered as the nodes of a weighted undirected graph. Each record pair is connected in the graph and the corresponding arc is weighted by the sum of field lengths of those fields which differ in the two records. The actual compression is made by constructing an MST of the graph and by storing it in an economic way to preserve the information of the file. The length of the MST is a useful measure in the estimation of the power of the compression. In the paper we study upper bounds of this length, especially in the case where the field lengths of the different fields may vary. The u…
Almost disjoint spanning trees: relaxing the conditions for completely independent spanning trees
2017
International audience; The search of spanning trees with interesting disjunction properties has led to the introduction of edge-disjoint spanning trees, independent spanning trees and more recently completely independent spanning trees. We group together these notions by dening (i, j)-disjoint spanning trees, where i (j, respectively) is the number of vertices (edges, respectively) that are shared by more than one tree. We illustrate how (i, j)-disjoint spanning trees provide some nuances between the existence of disjoint connected dominating sets and completely independent spanning trees. We prove that determining if there exist two (i, j)-disjoint spanning trees in a graph G is NP-comple…
Size-intensive decomposition of orbital energy denominators
2000
We introduce an alternative to Almlöf and Häser’s Laplace transform decomposition of orbital energy denominators used in obtaining reduced scaling algorithms in perturbation theory based methods. The new decomposition is based on the Cholesky decomposition of positive semidefinite matrices. We show that orbital denominators have a particular short and size-intensive Cholesky decomposition. The main advantage in using the Cholesky decomposition, besides the shorter expansion, is the systematic improvement of the results without the penalties encountered in the Laplace transform decomposition when changing the number of integration points in order to control the convergence. Applications will…
Method specific Cholesky decomposition : Coulomb and exchange energies
2008
We present a novel approach to the calculation of the Coulomb and exchange contributions to the total electronic energy in self consistent field and density functional theory. The numerical procedure is based on the Cholesky decomposition and involves decomposition of specific Hadamard product matrices that enter the energy expression. In this way, we determine an auxiliary basis and obtain a dramatic reduction in size as compared to the resolution of identity (RI) method. Although the auxiliary basis is determined from the energy expression, we have complete control of the errors in the gradient or Fock matrix. Another important advantage of this method specific Cholesky decomposition is t…
New insights into the OCST problem
2009
This paper considers the Euclidean variant of the optimal communciation spanning tree (OCST) problem. Researches have analyzed the structure of the problem and found that high quality solutions prefer edges of low cost. Further, edges pointing to the center of the network are more likely to be included in good solutions. We add to the literature and provide additional insights into the structure of the OCST problem. Therefore, we investigate properies of the whole tree, such as node degrees and the Wiener index. The results reveal that optimal solutions are structured in a star-like manner. There are few nodes with high node degrees, these nodes are located next to the graph's center. The m…